package com.github.hgkmail.hello.leetcode101.pointer.graph.shortestpath;

import com.google.common.collect.Lists;

import java.util.*;

//根据题意构建图，使用Map<String, Map<String, Double>>，再使用dfs进行查找。。。
//0.0 < values[i] <= 20.0
//最短路：BFS、Floyd、Dijkstra
public class LC399EvaluateDivision {

    public void dfs(Map<String, Map<String, Double>> graph, String start, String end, Set<String> visited, List<Double> found, Double curr) {
        if (!graph.containsKey(start) || !graph.containsKey(end) || !found.isEmpty()) {
            return;
        }
        visited.add(start);
        Map<String, Double> adjMap=graph.get(start);
        for (String adj:adjMap.keySet()) {
            if (visited.contains(adj)) {
                continue;
            }
            double origin=curr;
            curr = origin<0 ? adjMap.get(adj) : origin*adjMap.get(adj); //-1.0表示不存在
            if (adj.equals(end)) {
                found.add(curr);
                return;
            }
            dfs(graph, adj, end, visited, found, curr);
            curr=origin;
        }
        visited.remove(start);
    }

    //todo 用bfs查找路径，这个更符合题意，最短路
    //todo 用Floyd算法查找最短路
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int len=equations.size();
        if (len<=0) {
            return new double[]{};
        }
        //构建邻接矩阵
        Map<String, Map<String, Double>> graph=new HashMap<>();
        for (int i = 0; i < len; i++) {
            List<String> eq=equations.get(i);
            String a=eq.get(0);
            String b=eq.get(1);
            if (!graph.containsKey(a)) {
                graph.put(a, new HashMap<>());
            }
            graph.get(a).put(b, values[i]);
            //支持逆向查询，结果为倒数
            if (!graph.containsKey(b)) {
                graph.put(b, new HashMap<>());
            }
            graph.get(b).put(a, 1.0d/values[i]);
        }
        //进行查询
        List<Double> res=new ArrayList<>();
        List<Double> found = new ArrayList<>();
        Set<String> visited=new HashSet<>();
        for (List<String> q:queries) {
            String q1=q.get(0);
            String q2=q.get(1);
            if (q1.equals(q2)) {
                res.add(graph.containsKey(q1) ? 1.0d : -1.0d);
                continue;
            }

            found.clear();
            visited.clear();
            dfs(graph, q1, q2, visited, found, -1.0d);
            if (!found.isEmpty()) {
                res.add(found.get(0));
            } else {
                res.add(-1.0d);
            }
        }

        double[] resArr=new double[res.size()];
        for (int i = 0; i < resArr.length; i++) {
            resArr[i]=res.get(i);
        }
        return resArr;
    }

    public static void main(String[] args) {
        List<List<String>> equations=new ArrayList<>();
        equations.add(Lists.newArrayList("a","b"));
        equations.add(Lists.newArrayList("b","c"));
        double[] values=new double[]{2.0,3.0};
        List<List<String>> queries=new ArrayList<>();
        queries.add(Lists.newArrayList("a","c"));
        queries.add(Lists.newArrayList("b","a"));
        queries.add(Lists.newArrayList("a","e"));
        queries.add(Lists.newArrayList("a","a"));
        queries.add(Lists.newArrayList("x","x"));
        System.out.println(Arrays.toString(new LC399EvaluateDivision().calcEquation(equations, values, queries)));
    }
}
